Thực đơn
Sắp_xếp_nhanh Ví dụTrong ví dụ sau đây ta luôn chọn phần tử chốt là phần tử đứng giữa danh sách với chỉ số của phần tử chốt được chọn là k = i n t ( ( k 1 + k 2 ) / 2 ) {\displaystyle k=int((k_{1}+k_{2})/2)}
a = ( 2 , 6 , 3 , 7 , 4 , 5 , 1 ) {\displaystyle a=(2,6,3,7,4,5,1)}
2 | 6 | 3 | 7 | 4 | 5 | 1 |
Do ngẫu nhiên, phần tử chốt a [ 4 ] = 7 {\displaystyle a[4]=7} là phần tử lớn nhất trong dãy, ta tìm từ trái sang phải không có phần tử nào lớn hơn phần tử chốt, do đó ta đổi phần tử chốt với phần tử cuối cùng, danh sách được chia thành hai danh sách con a [ 1..6 ] {\displaystyle a[1..6]} và a [ 7..7 ] {\displaystyle a[7..7]}
2 | 6 | 3 | 1 | 4 | 5 | -- | 7 |
Việc phân chia tiếp tục với danh sách con a [ 1..6 ] {\displaystyle a[1..6]} . Phần tử chốt được chọn là a[4]=1. Từ trái sang phải tìm được phần tử đầu tiên lớn hơn a [ 4 ] = 1 {\displaystyle a[4]=1} là a [ 1 ] = 2 {\displaystyle a[1]=2} , từ phải sang phần tử đầu tiên <=1 là chính a[4]. Đổi chố hai phần tử này
1 | 6 | 3 | 2 | 4 | 5 | -- | 7 |
Đi tiếp sang phải ta được a [ 2 ] > 1 {\displaystyle a[2]>1} , ở phía ngược lại đi tiếp sang trái tìm được phần tử nhỏ hơn hoặc bằng chốt là chính a [ 1 ] = 1 {\displaystyle a[1]=1} nhưng lúc này hai đường đã chạm nhau nên ta không đổi nữa. Do vậy a [ 1..6 ] {\displaystyle a[1..6]} được phân chia thành hai danh sách con a [ 1..1 ] {\displaystyle a[1..1]} và a [ 2..6 ] {\displaystyle a[2..6]}
1 | -- | 6 | 3 | 2 | 4 | 5 | -- | 7 |
Tiếp tục phân chia a [ 2..6 ] {\displaystyle a[2..6]} với phần tử chốt a [ 4 ] = {\displaystyle a[4]=} 2 ta được
1 | -- | 2 | -- | 3 | 6 | 4 | 5 | -- | 7 |
Tiếp tục phân chia a [ 3..6 ] {\displaystyle a[3..6]} với phần tử chốt a [ 5 ] = 4 {\displaystyle a[5]=4} ta được
1 | -- | 2 | -- | 3 | 4 | -- | 6 | 5 | -- | 7 |
Tiếp tục phân chia a [ 3..4 ] {\displaystyle a[3..4]} với phần tử chốt a [ 4 ] = 4 {\displaystyle a[4]=4} và a [ 5..6 ] {\displaystyle a[5..6]} với phần tử chốt a [ 6 ] = 5 {\displaystyle a[6]=5} ta được
1 | -- | 2 | -- | 3 | -- | 4 | -- | 5 | -- | 6 | -- | 7 |
Thực đơn
Sắp_xếp_nhanh Ví dụLiên quan
Sắp xếp nổi bọt Sắp xếp trộn Sắp xếp chèn Sắp xếp nhanh Sắp xếp chọn Sắp xếp vun đống Sắp xếp tô pô Sắp xếp đếm phân phối Sắp xếp theo cơ số Sắp xếpTài liệu tham khảo
WikiPedia: Sắp_xếp_nhanh